Ray tracing has become mainstream in video game animation, motion picture and other media applications. Ray tracing describes a technique for synthesizing photorealistic images by identifying and summing paths connecting light sources with cameras. Rays are traced along the line of sight to determine visibility and from light sources to determine illumination.
A ray generally originates at a point in space described by a position vector and travels along a direction vector. Ray tracing is used in computer graphics to determine visibility by directing the ray from the origin along a line of sight described by the direction vector. The ray is tested for intersection against geometry within a virtual scene to determine the nearest visible surface along that line of sight.
Ray tracing generates an image by tracing the ray through pixels in a plane. The technique is capable of producing a very high degree of photorealism, usually higher than that of typical scanline rendering methods. Ray tracing is capable of simulating a wide variety of optical effects such as reflection and refraction, as well as scattering and chromatic aberration. Scenes may incorporate data from images and models captured by digital photography.
Such scenes in ray tracing are described mathematically by a programmer or visual artist using intermediary tools. For example, most ray tracing processes use an ADS, such as a k-dimensional tree (kd-tree), to generate three-dimensional images. A kd-tree may include empty leaf nodes that correspond to empty bounding volumes within a three-dimensional scene. A bounding volume may comprise a logically divided portion of the scene. A ray tracing algorithm may recursively split the scene by axis-aligned planes. Initially, the scene may be split in two by such a plane. Each resultant half may then be split again along some other plane(s). This results in a hierarchical organization of the kd-tree structure. Each level of the structure may be recursively traversed to determine where the next level of the tree may be found.
The leaf nodes of a kd-tree may include a small axis aligned cell that includes some number of polygons, or primitives. At the next level up the tree, each node represents an axis aligned box that is completely filled by some preset number of leaf nodes. As such, a split-plane splits the larger volume into the smaller leaf cells. At the next level, each node represents an axis aligned box completely filled by the lower level nodes using a similar split-plane. At any given level, a ray may be intersected against the bounding volumes to determine whether the ray misses, hits, refracts and/or reflects from an object.
Each ray is typically tested for intersection with some subset of all the objects in the scene. Once the nearest object has been identified, the algorithm will estimate the incoming light at the point of intersection and examine the material properties of the object. This information may be combined to calculate the final color of the pixel. Certain illumination algorithms and object materials may require more rays to be re-cast into the scene.
Despite the utility of ray tracing, current ray tracing techniques suffer from a number of known limitations and weaknesses. For example, algorithms used to build the ADS may experience slow setup of an ADS, as well as require relatively large amounts of processing and memory. These computing resources are thus unavailable to other aspects of a scene rendering processes. In some cases, more time may be spent building a tree than rendering the image. There are consequently diminishing returns for intelligently building an ADS.
Such challenges are exacerbated where view frustum culling should be used. View frustum culling is a process of removing objects that lie completely outside the viewing frustum from the rendering process. The frustum is the region of space in the modeled world that may appear on the screen, i.e., the field of view of the notional camera. Rendering these outlying objects might waste processing since they are not directly visible. Unlike with rasterization, view frustum culling in ray tracing is complicated because objects outside the viewing frustum may be visible when reflected off an object inside the frustum. To make culling fast, it usually must be accomplished using bounding volumes surrounding the objects rather than the objects themselves. The process remains relatively complex and often requires undesirable amounts of processing resources, which can burden the system.
There is consequently a need for an improved manner of rendering an image using ray tracing processes.